Maths and languages relation theory

"This text requires the mathematical maturity of a first year graduate student and is intended for a one or two-semester course. Useful background would be beginning courses in switching theory and sequential machines. Emphasis has been placed on concepts and ideas rather than trying to provide a definitive work, with the objective of giving the student a working knowledge of the major results and techniques of proof.

The book covers the concepts of a language, finite representations for a language, grammars including regular, context-free, LR(k), context-sensitive, and type 0, types of automata, pushdown automata, linear bounded automata, stack automata and Turing machines, properties of classes of languages, decidability results, procedures, algorithms, and computability. Among the specific topics included are the Chomsky and Greibach normal forms, self-embedding, ambiguity and inherent ambiguity in context-free languages, universal Turing machines, time and tape complexity classes, crossing sequences, Post's Correspondence Problem and the halting problem. The breadth of content makes this book unique in the field of language theory.

Library of Congress Catalog Card No. 69-14297